/**
 * 
 */
package solution.bit;

import junit.framework.Assert;

import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 * 
 */
public class SolutionCountBits {

	interface CountBits {
		int count(Integer i);
	}

	class CountBitsByAnd implements CountBits {
		/**
		 * count bits by using a mask.
		 */
		@Override
		public int count(Integer i) {
			// define the mask and the pattern
			// - the pattern is any number != 0
			int mask = 0x01;

			// the number of set-bits
			int n1s = 0;
			while (mask != 0) {
				// the pattern is any number != 0
				if ((i & mask) != 0) {
					n1s++;
				}
				mask <<= 1;
			}
			return n1s;
		}
	}

	class CountBitsByMinus implements CountBits {
		/**
		 * Count bits by 'minus'. Each loop will eliminate current last set-bit.
		 */
		@Override
		public int count(Integer i) {
			int n1s = 0;
			// For example, if i = 0x10, then i-1 will be 0x0F.
			// i & (i-1) will eliminate the last bit.
			// if (i & (i-1)) == 0 then i is of power of 2.
			while (i != 0) {
				n1s++;
				i &= (i - 1);
			}
			return n1s;
		}
	}

	class CountBitsByShift implements CountBits {
		/**
		 * count the set-bits by the 'mask'.
		 */
		@Override
		public int count(Integer i) {
			// define the mask and the pattern
			final int mask = 0x01;
			final int pattern = 0x01;

			// n1s: the number of set-bits
			int n1s = 0;
			while (i != 0) {
				// match the bit pattern.
				if ((i & mask) == pattern) {
					n1s++;
				}
				// left shift n bits, which is determined by the pattern
				i >>>= 1;
			}
			return n1s;
		}
	}

	@Test
	public void testNbits() {
		CountBits[] cbs = new CountBits[] { new CountBitsByAnd(),
				new CountBitsByMinus(), new CountBitsByShift() };
		for (CountBits cb : cbs) {
			Assert.assertEquals(0, cb.count(0));
			Assert.assertEquals(8, cb.count(0x5555));
			Assert.assertEquals(16, cb.count(0x55555555));
			Assert.assertEquals(32, cb.count(-1));
		}
	}
}
